{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Maximal Uncovered Ranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximalUncoveredRanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找最大长度的未覆盖区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给你一个长度为 n 的 <strong>索引从 0 开始的</strong>&nbsp;数组 <code>nums</code> 和一个 <strong>索引从 0 开始的</strong> 2 维数组 <code>ranges</code> ，<strong>ranges</strong> 是 <strong>nums</strong> 的子区间列表（子区间可能 <strong>重叠</strong> ）。</p>\n",
    "\n",
    "<p>每行 <code>ranges[i]</code> 恰好有两个元素：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ranges[i][0]</code> 表示第i个区间的起始位置（包含）</li>\n",
    "\t<li><code>ranges[i][1]</code> 表示第i个区间的结束位置（包含）</li>\n",
    "</ul>\n",
    "\n",
    "<p>这些区间覆盖了 <code>nums</code> 的一些元素，并留下了一些 <strong>未覆盖</strong> 的元素。你的任务是找到所有 <strong>最大长度</strong> 的未覆盖区间。</p>\n",
    "\n",
    "<p>返回按起始点 <strong>升序排序</strong> 的未覆盖区间的二维数组 <code>answer</code> 。</p>\n",
    "\n",
    "<p>所有 <strong>最大长度</strong> 的 <strong>未覆盖</strong> 区间指满足两个条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个未覆盖的元素应该属于 <strong>恰好</strong> 一个子区间。</li>\n",
    "\t<li><strong>不存在</strong>两个区间 (l1,r1) 和 (l2,r2) 使得 r1+1=l2 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 10, ranges = [[3,5],[7,8]]\n",
    "<b>输出：</b>[[0,2],[6,6],[9,9]]\n",
    "<b>解释：</b>区间 (3,5) 和 (7,8) 都被覆盖，因此如果我们将 nums 简化为一个二进制数组，其中 0 表示未覆盖的元素，1 表示覆盖的元素，则数组变为[0,0,0,1,1,1,0,1,1,0]，在其中我们可以观察到区间 (0,2)，(6,6)和(9,9)未被覆盖。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2&nbsp;：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, ranges = [[0,2]]\n",
    "<b>输出：</b>[]\n",
    "<strong>解释：</strong>在这个例子中，整个 nums 数组都被覆盖，没有未覆盖的元素，所以输出是一个空数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, ranges = [[2,4],[0,3]]\n",
    "<b>输出：</b>[[5,6]]\n",
    "<b>解释：</b>区间 (0,3) 和 (2,4) 都被覆盖，因此如果我们将 nums 简化为一个二进制数组，其中 0 表示未覆盖的元素，1 表示覆盖的元素，则数组变为[1,1,1,1,1,0,0]，在其中我们可以观察到区间 (5,6) 未被覆盖。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;=&nbsp;10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= ranges.length &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>ranges[i].length = 2</code></li>\n",
    "\t<li><code>0 &lt;= ranges[i][j] &lt;= n - 1</code></li>\n",
    "\t<li><code>ranges[i][0] &lt;=&nbsp;ranges[i][1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-maximal-uncovered-ranges](https://leetcode.cn/problems/find-maximal-uncovered-ranges/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-maximal-uncovered-ranges](https://leetcode.cn/problems/find-maximal-uncovered-ranges/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n[[3,5],[7,8]]', '3\\n[[0,2]]', '7\\n[[2,4],[0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        if len(intervals) == 0:\n",
    "            return []\n",
    "        intervals.sort(key=lambda x: -x[0])\n",
    "        ans = [intervals.pop()]\n",
    "        while intervals:\n",
    "            cur_start, cur_end = intervals.pop()\n",
    "            # 下一个区间的开始时间大于现在最晚的结束时间, 则新开始一个区间\n",
    "            if cur_start > ans[-1][1]: \n",
    "                ans.append([cur_start, cur_end])\n",
    "            # 下一个区间的开始时间小于等于现在的结束时间，则延长结束时间\n",
    "            else:\n",
    "                ans[-1][1] = max(ans[-1][1], cur_end)\n",
    "        return ans\n",
    "\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param ranges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        ranges = self.merge(ranges)\n",
    "\n",
    "        ret = []\n",
    "        st = 0\n",
    "        end = n - 1\n",
    "        for i in ranges:\n",
    "            if i[0] - 1 >= st:\n",
    "                ret.append([st, i[0] - 1])\n",
    "            st = i[1]+1\n",
    "        if st <= end:\n",
    "            ret.append([st, end])\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.findMaximalUncoveredRanges(n = 10, ranges = [[3,5],[7,8]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        ans = []\n",
    "        end = -1\n",
    "        for s, e in ranges:\n",
    "            if s - end > 1:\n",
    "                ans.append([end+1, s-1])\n",
    "            end = max(end, e)\n",
    "        if end < n-1:\n",
    "            ans.append([end+1, n-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        res, last = [], -1\n",
    "        for i,j in ranges + [[n,n]]:\n",
    "            if i > last + 1:\n",
    "                res.append([last+1, i-1])\n",
    "            last = max(last, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findMaximalUncoveredRanges(self, n, ranges):\n",
    "        ranges.sort()\n",
    "        res, c = [], 0\n",
    "        for left, r in ranges:\n",
    "            if c<left:\n",
    "                res.append([c, left-1])\n",
    "            if (t:=r+1)>c:c=t\n",
    "        return res+[[c, n-1]] if c<n else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        diffs = defaultdict(int)\n",
    "        height = 1\n",
    "        diffs[0] -= 1\n",
    "        diffs[n] += 1\n",
    "        for s,e in ranges:\n",
    "            diffs[s] += 1\n",
    "            diffs[e+1] -= 1\n",
    "\n",
    "        ans = []\n",
    "        prev = 0\n",
    "        for u in sorted(diffs):\n",
    "            if diffs[u] == 0:\n",
    "                continue\n",
    "            if height == 0:\n",
    "                ans.append([prev, u-1])\n",
    "            height += diffs[u]\n",
    "            if height == 0 :\n",
    "                prev = u\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        lines=sorted(ranges,key=lambda x:(x[0],x[1]))\n",
    "\n",
    "        dp=[]\n",
    "        new_line=[]\n",
    "        for line in lines:\n",
    "            if new_line==[]:\n",
    "                new_line=line\n",
    "            else:\n",
    "                if line[0]<=new_line[1]:\n",
    "                    new_line[1]=max(line[1],new_line[1])\n",
    "                else:\n",
    "                    dp.append(new_line[:])\n",
    "                    new_line=line\n",
    "        if new_line:\n",
    "            dp.append(new_line[:])\n",
    "        print(dp)\n",
    "        result=[]\n",
    "        left=0\n",
    "        right=-1\n",
    "        for d in dp:\n",
    "            right=d[0]-1\n",
    "            if right>=left:\n",
    "                result.append([left,right])\n",
    "            left=d[1]+1\n",
    "        \n",
    "        right=n-1\n",
    "        if right>=left:\n",
    "            result.append([left,right])\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        \n",
    "        m = len(ranges)\n",
    "        right = 0\n",
    "        ret = []\n",
    "        for s, e in ranges:\n",
    "            if s > right:\n",
    "                ret.append([right, s-1])\n",
    "                right = e + 1\n",
    "            else:\n",
    "                right = max(right, e+1)\n",
    "\n",
    "        if right < n:\n",
    "            ret.append([right,n-1])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        \n",
    "        m = len(ranges)\n",
    "        right = 0\n",
    "        ret = []\n",
    "        for r in ranges:\n",
    "            if r[0] > right:\n",
    "                ret.append([right, r[0]-1])\n",
    "                right = r[1] + 1\n",
    "            else:\n",
    "                right = max(right, r[1]+1)\n",
    "\n",
    "        if right < n:\n",
    "            ret.append([right,n-1])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        res, c = [], 0\n",
    "        for left, r in ranges:\n",
    "            if c < left:\n",
    "                res.append([c, left - 1])\n",
    "            if (t := r + 1) > c:c = t\n",
    "        return res + [[c, n - 1]] if c < n else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        ret = []\n",
    "        last_e = -1\n",
    "        for i in range(len(ranges)):\n",
    "            x, y = ranges[i]\n",
    "            if x > last_e + 1:\n",
    "                ret.append([last_e + 1, x - 1])\n",
    "            last_e = max(y, last_e)\n",
    "        if n > last_e + 1:\n",
    "            ret.append([last_e + 1, n - 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        res, c = [], 0\n",
    "        for left, r in ranges:\n",
    "            if c<left:\n",
    "                res.append([c, left-1])\n",
    "            if (t:=r+1)>c:c=t\n",
    "        return res+[[c, n-1]] if c<n else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        if not ranges:\n",
    "            return [[0, n - 1]]\n",
    "        dq = deque()\n",
    "        ranges.sort()\n",
    "        for x, y in ranges:\n",
    "            if dq and dq[-1][1] >= x:\n",
    "                a, b = dq.pop()\n",
    "                a, b = a, max(b, y)\n",
    "                dq.append([a, b])\n",
    "            else:\n",
    "                dq.append([x, y])\n",
    "        pre = 0\n",
    "        ans = []\n",
    "        for x, y in dq:\n",
    "            if pre < x:\n",
    "                ans.append([pre, x - 1])\n",
    "            pre = y + 1\n",
    "        if pre <= n - 1:\n",
    "            ans.append([pre, n - 1])\n",
    "        return ans \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\r\n",
    "        ranges.sort()\r\n",
    "        res, c = [], 0\r\n",
    "        for left, r in ranges:\r\n",
    "            if c<left:\r\n",
    "                res.append([c, left-1])\r\n",
    "            if (t:=r+1)>c:c=t\r\n",
    "        return res+[[c, n-1]] if c<n else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        stk = []\n",
    "        for l, r in sorted(ranges):\n",
    "            if stk and l <= stk[-1][1] + 1: stk[-1][1] = max(stk[-1][1], r)\n",
    "            else: stk.append([l, r])\n",
    "        ans = []\n",
    "\n",
    "        if not stk: return [[0, n - 1]]\n",
    "\n",
    "        for i, (l, r) in enumerate(stk):\n",
    "            if i == 0:\n",
    "                if l > 0: ans.append([0, l - 1])\n",
    "            else:\n",
    "                ans.append([stk[i - 1][1] + 1, l - 1])\n",
    "            \n",
    "            if i == len(stk) - 1:\n",
    "                if n - 1 > r: ans.append([r + 1, n - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort()\n",
    "        res, c = [], 0\n",
    "        for left, r in ranges:\n",
    "            if c<left:\n",
    "                res.append([c, left-1])\n",
    "            if (t:=r+1)>c:c=t\n",
    "        return res+[[c, n-1]] if c<n else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort(key=lambda x:(x[0],-x[1]))\n",
    "        \n",
    "        m = len(ranges)\n",
    "        right = 0\n",
    "        ret = []\n",
    "        for r in ranges:\n",
    "            if r[0] > right:\n",
    "                ret.append([right, r[0]-1])\n",
    "                right = r[1] + 1\n",
    "            else:\n",
    "                right = max(right, r[1]+1)\n",
    "\n",
    "        if right < n:\n",
    "            ret.append([right,n-1])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort(key=lambda x:(x[0],-x[1]))\n",
    "        \n",
    "        m = len(ranges)\n",
    "        r = 0\n",
    "        ret = []\n",
    "        for i in range(m):\n",
    "            if ranges[i][0] > r:\n",
    "                ret.append([r, ranges[i][0]-1])\n",
    "                r = ranges[i][1] + 1\n",
    "            else:\n",
    "                r = max(r, ranges[i][1]+1)\n",
    "\n",
    "        if r < n:\n",
    "            ret.append([r,n-1])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort(key=lambda x:(x[0],x[1]))\n",
    "        res = []\n",
    "        cur = 0\n",
    "        for left, right in ranges:\n",
    "            if cur < left:\n",
    "                res.append([cur, left - 1])\n",
    "            cur = max(cur, right + 1)\n",
    "        if cur < n:\n",
    "            res.append([cur, n - 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        ranges.sort(key=lambda x:x[0])\n",
    "        ans=[]\n",
    "        start=0\n",
    "        for left,right in ranges:\n",
    "            if start<left:\n",
    "                ans.append([start,left-1])\n",
    "            temp=right+1\n",
    "            if temp>start:\n",
    "                start=temp\n",
    "        if start<=n-1:\n",
    "            ans.append([start,n-1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:\n",
    "        D = defaultdict(int)\n",
    "        D[0] += 1\n",
    "        D[n] -= 1\n",
    "        for u, v in ranges:\n",
    "            D[u] += 1\n",
    "            D[v + 1] -= 1\n",
    "        \n",
    "        res = []\n",
    "        cur = pre = y = 0\n",
    "        for x in sorted(D):\n",
    "            if D[x] == 0: continue\n",
    "            if cur == 1:\n",
    "                res.append([y, x - 1])\n",
    "\n",
    "            cur += D[x]\n",
    "\n",
    "            if cur == 1:\n",
    "                y = x\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
